from LL import *
from copy import copy

def decompose(L1, L2, guardNode=None):
	"""
	Computes the intersection and symmetric difference of L1 and L2.
	If guardNode is set, both output will be guarded with a copy.
	"""
	if guardNode:
		(sd, it) = decompose_guarded(L1, L2, guardNode)
	else:
		(sd, it) = decompose_unguarded(L1, L2)
	return (it, sd)

def decompose_guarded(L1, L2, guardNode):
	"""
	Computes the symmetric difference and the intersection of L1 and L2.
	Both output will be guarded with a copy.
	>>> empty = toStandardGuardedLL([])
	>>> stg = getStandardGuard()
	>>> a = toStandardGuardedLL([1,5,7,9])
	>>> b = toStandardGuardedLL([2,5,7,8])
	>>> printEach(decompose_guarded(empty, empty, stg))
	inf -> *
	inf -> *
	>>> printEach(decompose_guarded(a, b, stg))
	1 -> 2 -> 8 -> 9 -> inf -> *
	5 -> 7 -> inf -> *
	>>> printEach(decompose_guarded(empty, b, stg))
	2 -> 5 -> 7 -> 8 -> inf -> *
	inf -> *
	>>> printEach(decompose_guarded(a, empty, stg))
	1 -> 5 -> 7 -> 9 -> inf -> *
	inf -> *
	"""
	(sd, sdP) = (copy(guardNode), None)
	(it, itP) = (copy(guardNode), None)
	while True:
		end1 = L1.v == guardNode.v
		end2 = L2.v == guardNode.v
		if end1 and end2:
			break
		elif end1 or (not end1 and L1.v>L2.v):
			(sd, sdP) = insert(sd, sdP, L2.v)
			L2 = L2.nx
		elif end2 or (not end2 and L1.v<L2.v):
			(sd, sdP) = insert(sd, sdP, L1.v)
			L1 = L1.nx
		else:
			(it, itP) = insert(it, itP, L1.v)
			(L1, L2) = (L1.nx, L2.nx)
	return (sd, it)

def decompose_unguarded(L1, L2):
	"""
	Computes the symmetric difference and the intersection of L1 and L2.
	>>> empty = toLL([])
	>>> a = toLL([1,5,7,9])
	>>> b = toLL([2,5,7,8])
	>>> printEach(decompose_unguarded(empty, empty))
	None
	None
	>>> printEach(decompose_unguarded(a, b))
	1 -> 2 -> 8 -> 9 -> *
	5 -> 7 -> *
	>>> printEach(decompose_unguarded(empty, b))
	2 -> 5 -> 7 -> 8 -> *
	None
	>>> printEach(decompose_unguarded(a, empty))
	1 -> 5 -> 7 -> 9 -> *
	None
	"""
	(sd, sdP) = (None, None)
	(it, itP) = (None, None)
	while L1 or L2:
		if (L1 and L2 and L1.v>L2.v) or (not L1 and L2):
			(sd, sdP) = insert(sd, sdP, L2.v)
			L2 = L2.nx
		elif (L1 and L2 and L1.v<L2.v) or (L1 and not L2):
			(sd, sdP) = insert(sd, sdP, L1.v)
			L1 = L1.nx
		elif L1 and L2: #equal
			(it, itP) = insert(it, itP, L1.v)
			(L1, L2) = (L1.nx, L2.nx)
	return (sd, it)


import doctest
doctest.testmod()
